1. Technical Field
This application relates to a system and method for processing digital map data. In particular, this application relates to a system and method for processing digital map data for route determination and determining a route between two points.
2. Related Art
Navigation systems have uses in may different areas that provide a user with information on how to reach a predetermined destination starting from a predetermined starting point. For example, navigation systems are implemented in handheld navigation devices. In addition, vehicles of all types, including land and marine vehicles, are increasingly equipped with navigation systems.
In a vehicle, a navigation system may assist the driver by providing driving instructions to a particular destination. The driver may input a desired destination, for example, by choosing a specific destination from a list of previously stored destinations provided by the device, or by entering destination coordinates. The navigation system determines the vehicle's current position, for example, by way of a global positioning system (GPS). The navigation system may also use additional items, for example movement sensors, to determine current position. The user of the navigation system also may manually input the location of the vehicle. Based on the starting point (the current position of the vehicle) and the desired destination point, the navigation system then determines a route for reaching the destination from the starting point, including, but not necessarily limited to information, for example, relating to the roads.
To navigate a route, a navigation system may use digital map data. In a land vehicle, such as a car or truck, the digital map may include road data. The map may also include information such as topographical information associated with the road data. The roads may be classified such that a navigation system using the digital map data may distinguish between a small road and a highway. With the starting and ending points and the digital map data, a navigation device may determine, based on predetermined criteria, how to reach the ending point. The route information may then be provided to the user in the form of all of the roads to be taken to reach the destination.
Route determination may be performed in a relatively small scale or “local” level, such as on the level of the roads. For example, in the context of a land vehicle such as a car, all possible roads within a region are considered when determining the route. When the starting point and desired destination are far from each other, route determination may require accessing and processing large amounts of data, resulting in costly and time consuming computations. Thus, there is a need for a navigation system that provides a simpler and faster determination of a route.